In a network of computing nodes, communication between the nodes may occur according to predefined rules, or may take place according to metrics based on current conditions of the network. Node coordination in networks, especially in ad-hoc networks, can be problematic. For example, when several nodes do not all have the same processing power, routing solely according to known or expected capacities of links between the nodes may not be efficient. Some networks are designed with variable levels of flexibility allowing some of their nodes to select a destination between peer nodes upon sending of messages or requests. In order to allow those networks to operate in an efficient manner, it becomes necessary to provide improved metrics enabling the nodes to make such selections.
A simple manner of balancing load on two co-processors is simply to allocate certain tasks on one processor and other tasks on the other processor. For example one central processing unit (CPU) on a personal computer might handle graphic display while the other CPU handles computation of input data. This sort of pre-arranged configuration is quite inefficient when, for example, a large amount of input data needs to be processed before any output can be graphically displayed.
Other processing load balancing methods rely on scanning of various processors to obtain a length of task queues waiting for treatment at each processor. This method may only be effective when the various processors are co-located, in the case of co-processors for example, and rely on one separate processor dedicated at least in part to running the scanning process.
Parallel scheduling is another approach for load balancing. In parallel scheduling methods, all processors cooperate to schedule work. Parallel scheduling balances load by using global load information at compile-time or runtime. These methods generally rely on a predetermined allocation of tasks to various processors, taking into account their relative processing capabilities. Parallel scheduling methods are hardly adaptable to changing conditions such as time varying requirements in terms of load imposed on the nodes.
A metric that is commonly used along with routing protocols to find an optimal computing path between two nodes is called minimum hop-count. Various paths between two nodes are compared and a number of discrete links, repeaters, routers and/or gateways are counted, yielding a number of hops per path. A given path on which the number of hops is smallest is selected as the optimal path for connecting the two nodes. When a first node has a choice of communicating with two or more peer nodes, the one of the peer nodes that may be reached using a minimum number of hops may be selected. Hence, minimum hop-count may be used to select one of a plurality of paths between two nodes, or may be used to select one of a plurality of peer nodes.
It has been shown that hop-count routing is not appropriate in an environment where nodes have different capabilities. For example, in “A High-Throughput Path Metric for Multi-Hop Wireless Routing”, D. S. J. De Couto et al., M.I.T. Computer Science and Artificial Intelligence Laboratory, International Conference on Mobile Computing and Networking, San Diego Calif., September 2003, authors demonstrate that minimum hop-count routing techniques have poor performance in some environments. They propose another metric, based on an expected transmission count, which is calculated using forward and reverse delivery ratios of links placed between two nodes. In contrast, other authors of “Comparison of Routing Metrics for Static Multi-Hop Wireless Networks”, R. Draves et al., Microsoft Research, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, Portland Oreg., August-September 2004, claim that hop-count metrics outperform other link-quality metrics when a sender of messages is mobile.
Nevertheless, prior art methods that rely on hop-count or on more advanced metrics to determine the best routing paths do not account for the fact that some nodes may have very high, or very low, traffic handling capabilities. Node coordination based solely on communication means between the nodes, not accounting for the capacity limits or current load of the nodes themselves, do not solve problems related to the exchange of metric information between nodes about their respective processing capacity, so that nodes can optimally use the capacity of a network.